package com;

public class Exercise3 {
    private static final int[][] SCORES = {{4, 0, 0, 0}, {3, 0, 0, 0}, {2, 0, 0, 0}, {1, 0, 0, 0}};

    public static void main(String[] args) {
        char[][] grid = {
                {'l', 'o', 'v', 'e'},
                {'o', 'v', 'e', 'l'},
                {'v', 'e', 'l', 'o'},
                {'e', 'l', 'o', 'v'}
        };
        System.out.println(maxScore(grid));
    }

    public static int maxScore(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        // 初始化 dp 数组的第一列和第一行
        for (int i = 0; i < m; i++) {
            dp[i][0] = getScore(grid[i][0]) + (i > 0 ? dp[i - 1][0] : 0);
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = getScore(grid[0][j]) + (j > 0 ? dp[0][j - 1] : 0);
        }

        // 动态规划填充 dp 数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = getScore(grid[i][j]) + Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m - 1][n - 1];
    }

    private static int getScore(char c) {
        switch (c) {
            case 'l':
                return SCORES[0][0];
            case 'o':
                return SCORES[1][0];
            case 'v':
                return SCORES[2][0];
            case 'e':
                return SCORES[3][0];
            default:
                return 0; // 如果有其他字符，不计分
        }
    }
}
